package line;

/**
 * 循环链表
 * 终端节点指针指回头节点
 * @author mengxin
 *
 * @param <E>
 */
public class CircularLinkedList<E> {
	private Node<E> head;
	private int length; // the length of the list

	public CircularLinkedList() {
		head = new Node<E>(null, head);
		length = 0;
	}

	/**
	 * 在头节点之前加一个节点
	 * @param item
	 */
	public void insertAtPrior(E item) {
		Node<E> node = new Node<E>(item, null); // encpsule the item to an node
		node.setNext(head.getNext()); // node.next = head.next
		head.setNext(node); // head.next = node
		length++;
	}

	public void add(E item) {// 在最后节点上添加一个节点
		Node<E> tmp = head;
		if (isEmpty()) { // if the list is null
			Node<E> node = new Node<E>(item, head); // .. if next == null ?
			head.setNext(node);
		} else {
			Node<E> node = new Node<E>(item, head);
			// find the end node of the list
			while (head != tmp.getNext()) {
				tmp = tmp.getNext();
			}
			tmp.setNext(node);
		}
		length++;
	}

	public E get(int index) { // 获取索引处的节点的数据
		// 先判断索引正确性
		if (index >= length || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		} else if (isEmpty()) {
			return null;
		} else {
			Node<E> tmp = head;
			int i = 0;
			while (head != tmp.getNext() && i <= index) {
				tmp = tmp.getNext();
				i++;
			}
			E e = tmp.getData();
			return e;
		}
	}

	public void insert(int index, E item) {// 在索引处后添加节点
		Node<E> node = new Node<E>(item, null);
		Node<E> tmp = head;
		int i = 1;

		if (index > length || index < 0) {
			System.out.println("the index is out of bounds");
		} else if (0 == length && 1 == index) {
			node.setNext(head);
			head.setNext(node);
			length++;
		} else {
			// find the node index
			while (head != tmp.getNext() && i <= index) {
				tmp = tmp.getNext();
				i++;
			}
			node.setNext(tmp.getNext());
			tmp.setNext(node);
			length++;
		}
	}

	/**
	 * 删除头节点
	 */
	public void removeFromFront() {
		Node<E> tmp = head;
		if (length < 1) {
			System.out
					.println("The list is null and you can not delete any node!");
		} else if (1 == length) {
			head.setNext(head);
			length--;
		} else {
			head.setNext(tmp.getNext().getNext());
			length--;
		}
	}

	public void remove(int index) {// 删除索引处的节点
		if (length < 1 || index > length) {
			System.out.println("index is out of bounds");
		} else if (1 == length && 1 == index) {
			head.setNext(head);
			length--;
		} else {
			Node<E> tmp = head;
			int i = 1;

			// get the node before index
			while (head != tmp.getNext() && i < index) {
				tmp = tmp.getNext();
				i++;
			}
			tmp.setNext(tmp.getNext().getNext());
			length--;
		}
	}

	/**
	 * 删除终端节点
	 */
	public void removeFromLast() {
		if (length < 1) { // if the list is null
			System.out.println("The list is null and you can not delete");
		} else if (1 == length) {
			head.setNext(head);
			length--;
		} else {
			Node<E> tmp1 = head;
			Node<E> tmp2 = head.getNext(); // set tmp2 -tmp1 = 1

			while (head != tmp2.getNext()) {
				tmp2 = tmp2.getNext();
				tmp1 = tmp1.getNext();
			}
			tmp1.setNext(head);
			length--;
		}
	}

	public int getLength() {
		return length;
	}

	public boolean isEmpty() {
		return length == 0;
	}

	public void display() {
		if (length < 1) {
			System.out.println("The list is null");
		} else {
			Node<E> tmp = head;
			while (head != tmp.getNext()) {
				tmp = tmp.getNext();
				System.out.print(tmp.getData() + " ");
			}
		}
	}

	// test the list
	public static void main(String[] args) {
		CircularLinkedList<Integer> cl = new CircularLinkedList<Integer>();
		System.out.println(cl.isEmpty());
		cl.add(1);
		cl.add(2);
		cl.insertAtPrior(3);
		cl.insert(2, 4);
		cl.add(5);
		System.out.println("the list is : ");
		cl.display();
		System.out.println();
		System.out.println("the length is :" + cl.getLength());
		cl.removeFromFront();
		cl.removeFromLast();
		cl.display();
		System.out.println();
		System.out.println("the length is :" + cl.getLength());
		System.out.println(cl.get(1));
	}

	class Node<E> {
		private Node<E> next;
		private E data;

		public Node(E data) {
			this.data = data;
			next = null;
		}

		public Node(E data, Node<E> nextNode) {
			this.data = data;
			next = nextNode;
		}

		public void setData(E data) {
			this.data = data;
		}

		public void setNext(Node<E> next) {
			this.next = next;
		}

		public E getData() {
			return data;
		}

		public Node<E> getNext() {
			return next;
		}
	}
}
